#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣687. 最长同值路径
// 【难度】中等
// 【提交】2025.10.14 https://leetcode.cn/problems/longest-univalue-path/submissions/670579530/
// 【标签】树；深度优先搜索；二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res;
    int longestUnivaluePath(TreeNode* root) {
        res = 0;
        if(!root) return 0;
        int ans = 0;
        dfs(root, ans);
        return res;
    }
    int dfs(TreeNode* root, int& ans) {
        if(root == nullptr) return 0;
        int l = dfs(root->left, ans);
        int r = dfs(root->right, ans);
        int l1 = 0, r1 = 0;
        if(root->left && root->left->val == root->val) {
            l1 += l + 1;
        }
        if(root->right && root->right->val == root->val) {
            r1 += r + 1;
        }
        res = max(res, l1 + r1);
        return max(l1, r1);
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个二叉树的根节点root，找出最长路径的长度，这个路径中的每个节点具有相同值。
 * 这条路径可以经过也可以不经过根节点。两个节点之间的路径长度由它们之间的边数表示。
 * 模型：树形DP，通过深度优先搜索计算每个节点的最长同值路径。
 * 
 * 二、标准解法状态设计
 * 1. 使用深度优先搜索遍历二叉树。
 * 2. 对于每个节点，计算以该节点为端点的最长同值路径（单侧）。
 * 3. 同时计算以该节点为转折点的最长同值路径（两侧），并更新全局最大值。
 * 4. 返回全局最大值作为结果。
 * 
 * 三、你的实现思路
 * 使用递归深度优先搜索，在遍历过程中维护两个值：
 * - 以当前节点为端点的最长同值路径（单侧）
 * - 以当前节点为转折点的最长同值路径（两侧）
 * 通过比较左右子树的同值路径，更新全局最大值。
 * 
 * 四、逐行注释（带细节提醒）
 * int res; // 全局变量记录最长路径
 * 
 * int longestUnivaluePath(TreeNode* root) {
 *     res = 0; // 初始化
 *     if(!root) return 0; // 空树处理
 *     int ans = 0; // 参数（实际未使用）
 *     dfs(root, ans); // 执行DFS
 *     return res; // 返回结果
 * }
 * 
 * int dfs(TreeNode* root, int& ans) {
 *     if(root == nullptr) return 0; // 递归终止条件
 *     
 *     int l = dfs(root->left, ans); // 左子树最长同值路径
 *     int r = dfs(root->right, ans); // 右子树最长同值路径
 *     
 *     int l1 = 0, r1 = 0; // 当前节点的左右延伸长度
 *     
 *     // 检查左子节点是否可以延伸
 *     if(root->left && root->left->val == root->val) {
 *         l1 = l + 1;
 *     }
 *     
 *     // 检查右子节点是否可以延伸
 *     if(root->right && root->right->val == root->val) {
 *         r1 = r + 1;
 *     }
 *     
 *     res = max(res, l1 + r1); // 更新全局最大值（两侧路径）
 *     return max(l1, r1); // 返回单侧最大值
 * }
 * 
 * 五、正确性证明
 * 算法通过深度优先搜索遍历所有节点，对于每个节点：
 * 1. 计算以该节点为端点的最长同值路径（只能选择左右子树中的一条路径）
 * 2. 计算以该节点为转折点的最长同值路径（可以同时包含左右子树）
 * 3. 全局变量res记录了遍历过程中遇到的最大路径长度
 * 由于遍历了所有节点，且每个节点都考虑了所有可能的最长路径情况，因此算法正确。
 * 
 * 六、复杂度
 * 时间：O(n)，其中n是树中的节点数，每个节点只被访问一次。
 * 空间：O(h)，其中h是树的高度，递归栈的深度。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需一次深度优先遍历；
 *   - 代码简洁，逻辑清晰；
 *   - 同时考虑了单侧路径和转折路径两种情况。
 * 缺点：
 *   - 使用了全局变量，可能不是纯函数；
 *   - 递归深度可能受树高度限制。
 * 
 * 八、改进建议
 * 1. 可以避免使用全局变量，通过引用参数传递结果；
 * 2. 可以移除未使用的ans参数；
 * 3. 对于教学场景，可以添加注释解释路径长度的计算方式。
 * 
 * 九、一句话总结
 * 通过深度优先搜索和树形动态规划，你的实现高效地解决了二叉树中最长同值路径问题，
 * 展现了递归思想在树结构问题中的应用能力。
 */